//题目：字母异位词分组

//题目解析：一个单词 abc 只要是bca cab都可以放在一个组
//输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

//思路解析：
// 由于互为字母异位词的两个字符串包含的字母相同
// 因此对两个字符串分别进行排序之后得到的字符串一定是相同的
// 故可以将排序之后的字符串作为哈希表的键

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<tr1/unordered_map>
#include <tr1/unordered_set>
//unordered_set相同
using namespace std::tr1;
//原先的std命名空间也不能省
using namespace std;
 vector<vector<string>> groupAnagrams(vector<string>& strs) {
    // 创建一个无序映射（unordered_map）来存储一组同字母异序词。
    // 键（key）是排序后的字符串（同字母异序词），
    //值（value）是原始字符串的向量，
    //这些字符串是同字母异序词。
    
    unordered_map<string,vector<string>>strVec;
    // 遍历输入向量中的每一个字符串
    for(auto str:strs)
    {
        // 创建原始字符串的副本，供后续结果向量使用
        string data=str;
        //核心：
        // 对字符串中的字符按照升序排序 比如ate eat排序之后 顺序都是2 那么就将这俩个字母同时插入 strVec[2] 
        sort(str.begin(),str.end());
        
        // 现在，排序后的 'str' 包含了同字母异序词的键。
        // 将原始字符串 'data' 添加到与同字母异序词键关联的向量中

        strVec[str].push_back(data);
    }
    vector<vector<string>> res;
    for(auto v:strVec)
    // 将原始字符串的向量（同字母异序词）添加到最终结果向量中
    res.push_back(v.second);
    // 返回最终结果，其中每个元素在结果向量中都是一组同字母异序词
    return res;
    }

int main() {
    vector<string> input = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result = groupAnagrams(input);

    cout << "Original Input:" << endl;
    for (const string& str : input) {
        cout << str << " ";
    }
    cout << endl;

    cout << "Grouped Anagrams:" << endl;
    for (const vector<string>& group : result) {
        for (const string& str : group) {
            cout << str << " ";
        }
        cout << endl;
    }

    return 0;
}